package NewCoder;

import java.util.ArrayList;
import java.util.List;

public class BM52 {
    //位运算
    //全部异或后的分组不好理解
    //分组依据就是两个数组哪一位不同就按照这一位分组，这一位为0的一组，这一位为1的一组
    //而全部异或的结果tmp就说明了这两个数字的哪一位不同也就是我们分组的依据
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        //先将全部数进行异或运算，得出最终结果
        int tmp=0;
        for(int num:array){
            tmp^=num;
        }

        //找到那个可以充当分组去进行运算的数
        //从最低位开始找起
        int mask=1;
        while((tmp&mask)==0){
            mask<<=1;
        }

        //进行分组，分成两组，转换成两组 求出现一次的数组
        int a=0;
        int b=0;
        for(int num:array){
            if((num&mask)==0){
                a^=num;
            }else{
                b^=num;
            }
        }
        //因为题目要求小的数放前面，所以进行判断
        if(a>b){
            int c=a;
            a=b;
            b=c;
        }
        return new int[]{a,b};
    }


    //借助哈希表来记录数字出现的次数，最终再遍历这个哈希表（数组），得到只出现一次的两个数字
//    public int[] FindNumsAppearOnce (int[] array) {
//        // write code here
//        int[] arr=new int[1000001];
//        List<Integer> list=new ArrayList<>();
//        int[] res=new int[2];
//        for(int i=0;i<array.length;i++){
//            arr[array[i]]++;
//        }
//        for(int i=0;i<arr.length;i++){
//            if(arr[i]==1){
//                list.add(i);
//            }
//        }
//        for(int i=0;i<list.size();i++){
//            res[i]=list.get(i);
//        }
//        return res;
//    }
}
